package cn.hy.today;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution_1466 {

    List<int[]>[] g;


    /**
     * 我们不妨考虑从节点 0 出发，到达其他所有节点。方向与题目描述相反，意味着我们在构建图的时候，
     * 对于有向边 [a,b]，我们应该视为有向边 [b,a]。也即是说，如果要从 a 到 b，我们需要变更一次方向；
     * 如果要从 b 到 a，则不需要变更方向。
     */
    public int minReorder(int n, int[][] connections) {
        g = new List[n];
        // 这个设置值有问题
//        Arrays.fill(g, new ArrayList<>());
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] connection : connections) {
            int a = connection[0];
            int b = connection[1];
            g[a].add(new int[]{b, 1});
            g[b].add(new int[]{a, 0});
        }
        int ans = dfs(0, -1);
        return ans;
    }


    public int dfs(int a, int fa) {
        int ans = 0;
        for (int[] edg : g[a]) {
            int b = edg[0], c = edg[1];
            if (b != fa) {
                ans += c + dfs(b, a);
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[][] c = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
        int n = 6;
        Solution_1466 s = new Solution_1466();
        int i = s.minReorder(n, c);

        System.out.println("i = " + i);
    }

}